package com.code.test.dance;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0763.%E5%88%92%E5%88%86%E5%AD%97%E6%AF%8D%E5%8C%BA%E9%97%B4.md
 * 字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。
 * <p>
 * 示例：
 * <p>
 * 输入：S = "ababcbacadefegdehijhklij"
 * 输出：[9,7,8] 解释： 划分结果为 "ababcbaca", "defegde", "hijhklij"。 每个字母最多出现在一个片段中。 像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。
 * 提示：
 * <p>
 * S的长度在[1, 500]之间。
 * S只包含小写字母 'a' 到 'z' 。
 */
public class CodeZimu {

    public static void main(String[] args) {
        String s = "ababcbacadefegdehijhklij";
        List<Integer> ret = partitionLabels(s);
        System.out.println(ret);
    }


    /**
     * 重点在于同一字母最多出现在一个片段中，即同一字母第一次出现的下标位置和最后一次出现的下标位置肯定出现在同一个片段中
     * <p>
     * 1、先遍历一遍字符串，用哈希表记录下每个字母最后一次出现的位置
     * 2、
     */
    public static List<Integer> partitionLabels(String s) {
        List<Integer> ret = new ArrayList<>();
        char[] ch = s.toCharArray();
        int[] hash = new int[26];
        for (int i = 0; i < ch.length; i++) {
            //字母的最后出现位置
            hash[ch[i] - 'a'] = i;
        }

        int idx = 0;
        int last = -1;
        for (int i = 0; i < ch.length; i++) {
            //找到当前字母最后出现的位置,然后跟idx比大小
            idx = Math.max(idx, hash[ch[i] - 'a']);
            //如果最远距离==i
            if (i == idx) {
                ret.add(i - last);
                last = i;
            }
        }
        return ret;
    }


}
